#define _CRT_SECURE_NO_WARNINGS
#include"sort.h"
#include"stack.h"
void Swap(int* a, int* b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void BubbleSort(int* a, int n) {
	for (int i = 0; i < n - 1; i++) {
		int flag = 0;
		for (int j = 0; j < n - 1 - i; j++) {
			if (a[j] > a[j + 1]) {
				Swap(&a[j], &a[j + 1]);
				flag = 1;
			}
		}
		if (flag == 0) {
			break;
		}
	}
}

void InsertSort(int* a, int n) {
	for (int i = 1; i < n; i++) {
		int tmp = a[i];
		int end = i - 1;
		while (end >= 0) {
			if (a[end] > tmp) {
				a[end + 1] = a[end];
			}
			else {
				break;
			}
			end--;
		}
		a[end + 1] = tmp;
	}
}

//void ShellSort(int* a, int n) {
//	int gap = n/2;
//	while (gap >= 1) {
//		for (int i = 0; i < n - gap; i++) {
//			int tmp = a[i + gap];
//			int end = i;
//			while (end >= 0) {
//				if (tmp < a[end]) {
//					a[end + gap] = a[end];
//				}
//				else {
//					break;
//				}
//				end -= gap;
//			}
//			a[end + gap] = tmp;
//		}
//		gap /= 2;
//	}
//}

void ShellSort(int* a, int n) {
	//int gap = n / 2;
	int gap = n;
	while (gap > 1) {
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++) {
			int tmp = a[i + gap];
			int end = i;
			while (end >= 0) {
				if (tmp < a[end]) {
					a[end + gap] = a[end];
				}
				else {
					break;
				}
				end -= gap;
			}
			a[end + gap] = tmp;
		}
		gap /= 2;
	}
}


//void SelectSort(int* a, int n) {
//	for (int i = 0; i < n - 1; i++) {
//		int mini = i;
//		for (int j = i + 1; j < n; j++) {
//			if (a[j] < a[mini]) {
//				mini = j;
//			}
//		}
//		Swap(&a[mini], &a[i]);
//	}
//}

//void SelectSort(int* a, int n) {
//	int left = 0;
//	int right = n - 1;
//	while (left < right) {
//		int maxi = left;
//		int mini = left;
//		for (int i = left; i <= right; i++) {
//			if (a[i] < a[mini]) {
//				mini = i;
//			}
//			if (a[i] > a[maxi]) {
//				maxi = i;
//			}
//		}
//		Swap(&a[left], &a[mini]);
//		if (left == maxi) {
//			maxi = mini;
//		}
//		Swap(&a[right], &a[maxi]);
//		left++;
//		right--;
//	}
//}
void SelectSort(int* a, int n) {
	int left = 0;
	int right = n - 1;
	while (left < right) {
		int maxi = left;
		int mini = right;
		for (int i = left; i <= right; i++) {
			if (a[i] > a[maxi]) {
				maxi = i;
			}
			if (a[i] < a[mini]) {
				mini = i;
			}
		}
		Swap(&a[left], &a[mini]);
		if (maxi == left) {
			maxi = mini;
		}
		Swap(&a[right], &a[maxi]);
		left++;
		right--;
	}
}


//
//void QuickSort1(int* a, int begin, int end) {
//	if (begin >= end) {
//		return;
//	}
//	int keyi = begin;
//	int left = begin;
//	int right = end;
//	while (left < right) {
//		while (left < right && a[right] >= a[keyi]) {
//			right--;
//		}
//		while (left < right && a[left] <= a[keyi]) {
//			left++;
//		}
//		Swap(&a[left], &a[right]);
//	}
//	Swap(&a[keyi], &a[left]);
//	QuickSort1(a, begin, left - 1);
//	QuickSort1(a, left + 1, end);
//}
void QuickSort1(int* a, int begin, int end) {
	if (begin >= end)
		return;
	int keyi = begin;
	int left = begin;
	int right = end;
	while (left < right) {
		while (a[right] >= a[keyi]&&left<right) {
			right--;
		}
		while (a[left] <= a[keyi]&&left<right) {
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[left]);
	QuickSort1(a, begin, left - 1);
	QuickSort1(a, left + 1, end);
}


//void QuickSort2(int* a, int begin, int end) {
//	if (begin >= end)
//		return;
//	int tmp = a[begin];
//	int pit = begin;
//	int left = begin;
//	int right = end;
//	while (left < right) {
//		while (a[right] >= tmp && left < right) {
//			right--;
//		}
//		Swap(&a[pit], &a[right]);
//		pit = right;
//		while (a[left] <= tmp && left < right) {
//			left++;
//		}
//		Swap(&a[pit], &a[left]);
//		pit = left;
//	}
//	QuickSort2(a, begin, pit - 1);
//	QuickSort2(a, pit + 1, end);
//}
void QuickSort2(int* a, int begin, int end) {
	if (begin >= end)
		return;
	int tmp = a[begin];
	int pit = begin;
	int left = begin;
	int right = end;
	while (left < right) {
		while (left < right && a[right] >= tmp) {
			right--;
		}
		a[pit] = a[right];
		pit = right;
		while (left < right && a[left] <= tmp) {
			left++;
		}
		a[pit] = a[left];
		pit = left;
	}
	a[pit] = tmp;
	QuickSort2(a, begin, pit - 1);
	QuickSort2(a, pit + 1, end);
}



//void QuickSort3(int* a, int begin, int end) {
//	if (begin >= end)
//		return;
//	int keyi = begin;
//	int left = begin + 1;
//	int right = begin + 1;
//	while (right <= end) {
//		while (a[right] >= a[keyi]&&right<=end) {
//			right++;
//		}
//		if (a[right] < a[keyi]&&right<=end) {
//			if (left != right) {
//				Swap(&a[left], &a[right]);
//			}
//			right++;
//			left++;
//		}
//	}
//	Swap(&a[left - 1], &a[keyi]);
//	QuickSort3(a, begin, left - 2);
//	QuickSort3(a, left, end);
//}

void QuickSort3(int* a, int begin, int end) {
	if (begin >= end)
		return;
	int tmp = a[begin];
	int left = begin;
	int right = begin + 1;
	while (right <= end) {
		if (a[right] < tmp&&left++!=right) {
			Swap(&a[left], &a[right]);
		}
		right++;
	}
	Swap(&a[left], &a[begin]);
	QuickSort3(a, begin, left - 1);
	QuickSort3(a, left + 1, end);
}

void QuickSortNonR(int* a, int begin, int end) {
	ST st;
	STInit(&st);
	STPush(&st, end);
	STPush(&st, begin);
	while (!STEmpty(&st)) {
		int left = STTop(&st);
		STPop(&st);
		int right = STTop(&st);
		STPop(&st);
		int tmp = a[left];
		int left1 = left;
		int right1 = right;
		while (left < right) {
			while (left < right && a[right] >= tmp) {
				right--;
			}
			while (left < right && a[left] <= tmp) {
				left++;
			}
			Swap(&a[left], &a[right]);
		}
		Swap(&a[left1], &a[left]);
		if (left1 < left - 1) {
			STPush(&st, left-1);
			STPush(&st, left1);
		}
		if (left+1 < right1) {
			STPush(&st, right1);
			STPush(&st, left + 1);
		}
	}
}
void _MergeSort(int* a, int* tmp, int begin, int end) {
	if (begin >= end)
		return;
	int mid = (begin + end) / 2;
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	_MergeSort(a, tmp, begin1, end1);
	_MergeSort(a, tmp, begin2, end2);
	int cur = begin;
	while (begin1 <= end1 && begin2 <= end2) {
		if (a[begin1] < a[begin2]) {
			tmp[cur++] = a[begin1++];
		}
		else {
			tmp[cur++] = a[begin2++];
		}
	}
	while (begin1 <= end1) {
		tmp[cur++] = a[begin1++];
	}
	while (begin2 <= end2) {
		tmp[cur++] = a[begin2++];
	}
	memcpy(a+begin, tmp+begin, sizeof(int)*(end - begin + 1));

}
void MergeSort(int* a, int n) {
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL) {
		perror("malloc failed");
		exit(-1);
	}
	_MergeSort(a, tmp, 0, n - 1);
	free(tmp);
}

void MergeSortNonR(int* a, int n) {
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL) {
		perror("malloc failed");
		exit(-1);
	}
	int gap = 1;
	while (gap < n) {
		gap *= 2;
		for (int i = 0; i < n; i += gap) {
			int begin1 = i;
			int begin2 = i + gap / 2;
			int end1 = begin2 - 1;
			int end2 = begin2 + end1 - begin1;
			if (begin2 >= n) {
				break;
			}
			if (end2 >= n) {
				end2 = n - 1;
			}
			int cur = begin1;
			while (begin1 <= end1 && begin2 <= end2) {
				if (a[begin1] < a[begin2]) {
					tmp[cur++] = a[begin1++];
				}
				else {
					tmp[cur++] = a[begin2++];
				}
			}
			while (begin1 <= end1) {
				tmp[cur++] = a[begin1++];
			}
			while (begin2 <= end2) {
				tmp[cur++] = a[begin2++];
			}
			memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));
		}
	}
}

void CountSort(int* a, int n) {
	int max = a[0];
	int min = a[0];
	for (int i = 0; i < n; i++) {
		if (a[i] < min) {
			min = a[i];
		}
		if (a[i] > max) {
			max = a[i];
		}
	}
	int num = max - min + 1;
	int* tmp = (int*)malloc(sizeof(int) * num);
	if (tmp == NULL) {
		perror("malloc fail");
		exit(-1);
	}
	memset(tmp, 0, sizeof(int) * num);
	for (int i = 0; i < n; i++) {
 		tmp[a[i] - min]++;
	}
	int j = 0;
	int k = 0;
	while (j < num) {
		while (tmp[j] == 0) {
			j++;
		}
		if (j < num) {
			a[k] = j + min;
			k++;
			tmp[j]--;
		}
		
	}
}